package Deque;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;

public class Stack {



    boolean isValid(String s) {
        Deque<Character> deq = new ArrayDeque<>();
        for(char c:s.toCharArray()){
            if(c=='(' || c=='[' || c=='{' ) deq.push(c);
            else{
                if(deq.isEmpty()) return false;
                char c1 = deq.poll();
                if(c1 =='(' && c == ')'
                        || c1=='[' && c == ']'
                        || c1=='{' && c == '}' ){
                    continue;
                }
                return  false;
            }
        }
        return deq.isEmpty();
    }
    public String removeDuplicates(String s) {
        Deque<Character> deq = new ArrayDeque<>();
        for(char c:s.toCharArray()){
            if(deq.isEmpty()||deq.peek()!=c){
                deq.push(c);
            }
            else{
                deq.pop();
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!deq.isEmpty()){
            sb.insert(sb.length(),deq.pop());
        }
        return sb.toString();
    }
    @Test
    public void evalRPN() {
        String[] tokens = new String[]{"1","2","+"};
        Deque<String> deq = new ArrayDeque<>();
        for(String token:tokens){
            if(isNumber(token)){
                deq.push(token);
            }
            else{
                int b = Integer.parseInt(deq.pop());
                int a = Integer.parseInt(deq.pop());
                if(token.equals("+")){
                    deq.push(String.valueOf(a + b));
                    }
                else if(token.equals("-")){
                    deq.push(String.valueOf(a - b));
                }
                else if(token.equals("*")){
                    deq.push(String.valueOf(a * b));
                }
                else{
                    deq.push(String.valueOf(a / b));

                }
            }
        }
        System.out.println(Integer.parseInt(deq.pop()));
    }
    boolean isNumber(String s){
        return s.charAt(s.length() - 1) <'0';
    }
}
class MyStack {
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();
    public MyStack() {

    }

    public void push(int x) {
        if (q1.isEmpty() ) {
            q1.offer(x);
            while(!q2.isEmpty()){
                q1.offer(q2.poll());
            }
        }
        else {
            q2.offer(x);
            while(!q1.isEmpty()){
                q2.offer(q1.poll());
            }
        }
    }

    public int pop() {
        if (q1.isEmpty() && q2.isEmpty()) {
            return -1;
        }
        else if(q1.isEmpty()){
            return q2.poll();
        }
        else {
            return q1.poll();
        }
    }

    public int top() {
        if (q1.isEmpty() && q2.isEmpty()) {
            return -1;
        }
        else if(q1.isEmpty()){
            return q2.peek();
        }
        else {
            return q1.peek();
        }
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */